|
Iterative compression is an algorithmic technique invented by Reed, Smith and Vetta to show that the problem Odd Cycle Transversal was solvable in time ''O''(3''k'' ''kmn''). Odd Cycle Transversal was a longstanding central open question in parameterized complexity. This technique later proved very useful in showing fixed-parameter tractability results. It is now considered to be one of the fundamental techniques in the area of parameterized algorithmics. Iterative compression has been used successfully in many problems, for instance odd cycle transversal (see below) and edge bipartization, feedback vertex set, cluster vertex deletion and directed feedback vertex set. It has also been used successfully for exact exponential time algorithms for independent set. ==Technique== Consider a graph problem whose inputs are a graph ''G'' = (''V'',''E'') and a natural number ''k''. Suppose furthermore that the solution ''X'' of vertices has the constraint |''X''| ≤ ''k'', and that the problem is closed under induced subgraphs. In ''iterative compression'', a ''compression'' variant of the problem is one where a solution ''Y'' of size ''k'' + 1 must be compressed to a solution of size ''k''. If there exists a compression variant of the problem it can be applied ''iteratively'' on larger induced subgraphs ''G''1 ⊂ ''G''2 ⊂ ''G''3 ⊂ ··· ⊂ ''G''''n'', where ⊂ denotes induced subgraphs, each time obtaining a compressed solution ''Y'' of size ''k''. Then the newly introduced vertex is added to ''Y'', leading to a solution of size ''k'' + 1. This allows the compression algorithm to be applied again. In total, this adds a linear factor overhead over the compression algorithm. Therefore, if the compression variant is solvable in fixed-parameter tractable time, i.e., ''f''(''k'') · ''n''''c'' for some constant ''c'', then the iterative compression procedure solving the entire problem runs in ''f''(''k'') · ''n''''c''+1 time. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Iterative compression」の詳細全文を読む スポンサード リンク
|